singularity

singularity 🔎

141. ✅ Linked List Cycle

O(n)

• using set()

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        nodes = set()
        curr = head
        while curr:
            if curr in nodes:
                return True
            nodes.add(curr)
            curr = curr.next
        return False

• using [two pointers]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        fast = head
        slow = head 

        while fast != slow:
            slow = slow.next
            fast = fast.next.next 

            if fast == slow:
                return True

        return False

impl Solution {
    pub fn has_cycle(head: Option<Box<ListNode>>) -> bool {
        let mut slow = &head;
        let mut fast = &head;
        
        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
            slow = &slow.as_ref().unwrap().next;
            fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
            
            if std::ptr::eq(slow as *const _, fast as *const _) {
                return true;
            }
        }
        
        false
    }
}